#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<string>> res;

    void NQueens(vector<string> Queens, int n, map<int, int> hash_H, map<int, int> hash_L, map<int, int> hash_F, map<int, int> hash_Z)
    {
        if (n == 0)
        {
            res.push_back(Queens);
            return;
        }
        int H = Queens.size();
        int L = H;
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < L; j++)
            {
                if (hash_H[i] != 1 && hash_L[j] != 1)
                {
                    Queens[i][j] = 'Q';
                    hash_H[i] = 1;
                    hash_L[j] = 1;
                    hash_F[i + j] = 1;
                    hash_Z[i - j] = 1;
                    NQueens(Queens, n - 1, hash_H, hash_L, hash_F, hash_Z);
                    hash_H[i] = 0;
                    hash_L[j] = 0;
                    Queens[i][j] = '.';
                    hash_F[i + j] = 0;
                    hash_Z[i - j] = 0;
                }
            }
            // hash_H[i] = 0;
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        //思路:往n*n的棋盘房值,放了一个值之后,当前的行和列的hash值为1
        //遍历的去放,如果到达(n-1)(n-1)的位置,切n个皇后都被防止则存到res
        vector<string> Queens;
        //初始化棋盘
        map<int, int> hash_H;
        map<int, int> hash_L;
        map<int, int> hash_F;
        map<int, int> hash_Z;
        int N = n / 2 + 1;
        for (int i = 0; i < N; i++)
        {
            hash_F[i] = 0;
            // hash_Z[i] = 0;
        }
        for(int i = -N;i<N;i++){
            hash_Z[i] = 0;
        }
        for (int i = 0; i < n; i++)
        {
            hash_H[i] = 0;
            hash_L[i] = 0;
            string tmp;
            for (int j = 0; j < n; j++)
            {
                tmp += ".";
            }
            Queens.push_back(tmp);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (hash_H[i] != 1 && hash_L[j] != 1, hash_F[i + j] != 1, hash_Z[i - j] != 1)
                {
                    // for(int )
                    Queens[i][j] = 'Q';
                    hash_H[i] = 1;
                    hash_L[j] = 1;
                    hash_F[i + j] = 1;
                    hash_Z[i - j] = 1;
                    NQueens(Queens, n - 1, hash_H, hash_L, hash_F, hash_Z);
                    hash_H[i] = 0;
                    hash_L[j] = 0;
                    Queens[i][j] = '.';
                    hash_F[i + j] = 0;
                    hash_Z[i - j] = 0;
                }
            }
            // hash_H[i] = 0;
        }
        // for(int i = 0;i<res.size();i++){
        //     sort(res[i].begin(),res[i].end());
        // }
        // sort(res.begin(), res.end());
        // set<vector<string>> ress(res.begin(), res.end());
        // res.assign(ress.begin(), ress.end());
        return res;
    }
};